/**
 * 
 */
package hunau.edu.cxb20.practice4_2Sort;

/**
 * @author Jiang Zhiyan
 *
 * 2021年4月7日 下午9:30:38
 */
public class InsertionSort {
 public  static void main (String args[]) {
	 int [] arr= {4,6,2,8,5,1,3,9};
//	 insertionSort(arr);
	 insertionSort(arr);
	 print(arr);
 }
 
	
	  public static void insertionSort(int [] arr) { 
		  for(int i=1;i<arr.length;i++) { //右边第二部分数
			  int j=i-1; 
			  int data=arr[i]; //将第二部分的第一个数先存起来
	  for(;j>=0;j--) {   //左边数的范围
		   if(data<arr[j]) { //判断，如果第二部分数小于左侧第一部分数 不能用arr[i]<arr[j]
			   arr[j+1]=arr[j]; //将数大的一个向右移一位
		   }else {
			   break;
		   }
	  }  
//	  System.out.println(j-1);
		  arr[j+1]=data; //此处用j-1是因为在循环之后得到的值是j--之后的值，相当于比原计划的值减去了1，因此要加回来
	  } 
	  }
	 
 public static void insertionSort1(int [] arr) {
	 for(int i=1;i<arr.length-1;i++) { //第二部分的第一个数
		 for(int j=i-1;j>=0;j--) { //第一部分 数不断增多
		if(arr[j+1]<arr[j]) {
			int change =arr[j];
			arr[j]=arr[j+1];
			arr[j+1]=change;
		}
		 }
	 }
 };
 public static void print(int [] arr) {
	 for(int i:arr) {
		 System.out.print(i+"\t");
	 }
 }
}
